package www.study.com;

//最长回文子串 https://leetcode.cn/problems/longest-palindromic-substring/
public class code5 {
    public static void main(String[] args) {

    }

    //其他方式：暴力 - 0（n^2），动态规划 - 0（n^2）
    //方式一：manacher算法   时间复杂度0（n）
    class Solution {
        public String longestPalindrome(String s) {
            char[] chs = toManacher(s);
            int[] arr = new int[chs.length];
            arr[0] = 1;
            int point = 0;
            int nextRange = 1;
            int maxPoint = 0;
            int r = 0;
            for (int i = 1; i < chs.length; i++) {
                //System.out.print("  i : " + (i - 1) + ":" + arr[i - 1]);
                r = nextRange - i;
                if(2 * point - i >= 0) r = Math.min(arr[2 * point - i] , r);
                while ((i - r >= 0) && (i + r < chs.length) && (chs[i - r] == chs[i + r])){
                    r++;
                }
                arr[i] = r;
                if (i + r > nextRange){
                    point = i;
                    nextRange = i + r;
                }
                if (arr[i] > arr[maxPoint]){
                    maxPoint = i;
                }
            }
            // System.out.println(arr[maxPoint]);
            // System.out.println(String.valueOf(chs));
            // System.out.println(maxPoint);
            String res = String.valueOf(chs).substring(maxPoint - arr[maxPoint] + 1,maxPoint + arr[maxPoint]).replaceAll("#","");
            return res;
        }
        public char[] toManacher(String s){
            char[] chs = new char[s.length() * 2 + 1];
            int index = 0;
            for (int i = 0; i < chs.length; i++) {
                if ((i & 1) == 0){
                    chs[i] = '#';
                }else{
                    chs[i] = s.charAt(index++);
                }
            }
            return chs;
        }
    }
}
